package name.huzhenbo.java.algorithm.graph;

import java.util.List;
import java.util.ArrayList;

class Graph {
    private int vertexNum;
    private int[][] vertexArcs;
    private boolean[] deletedVexes;

    private Graph(Builder builder) {
        this.vertexNum = builder.vertexNum;
        this.vertexArcs = builder.vertexArcs;
        this.deletedVexes = new boolean[vertexNum];
    }

    public void addArc(int v1, int v2, int weight) {
        vertexArcs[v1][v2] = weight;
    }

    public int vertexNum() {
        return vertexNum;
    }

    public int firstAdjVex(int v) {
        return nextAdjVex(v, -1);
    }

    public int nextAdjVex(int v, int w) {
        int[] relations = vertexArcs[v];
        for (int i = w + 1; i < relations.length; i++) {
            if (relations[i] >= 1) {
                return i;
            }
        }
        return -1;
    }

    /**
     * If same node, return 0
     * If different node, and has relation, return weight
     * If different node, and has no relation, return -1
     *
     * @param start
     * @param end
     * @return
     */
    public int weight(int start, int end) {
        return start == end ? 0 : vertexArcs[start][end];
    }

    public List<Integer> vexesWithoutIn() {
        List<Integer> leftVexes = new ArrayList<Integer>();
        for (int i = 0; i < vertexNum(); i++) {
            if (!deletedVexes[i]) leftVexes.add(i);
        }
        for (int i = 0; i < vertexArcs.length; i++) {
            int w = firstAdjVex(i);
            while (w != -1) {
                if (leftVexes.contains(w)) leftVexes.remove(leftVexes.indexOf(w));
                w = nextAdjVex(i, w);
            }
        }
        return leftVexes;
    }

    public void remove(int vex) {
        for (int i = 0; i < vertexArcs.length; i++) {
            vertexArcs[i][vex] = -1;
            vertexArcs[vex][i] = -1;
        }
        deletedVexes[vex] = true;
    }

    public int deletedVertexNum() {
        int count = 0;
        for (boolean deleted : deletedVexes) {
            if (deleted) count++;
        }
        return count;
    }

    public static Graph newInstance(Graph graph) {
        Builder builder = new Builder(graph.vertexNum);
        // Array clone is shallow clone, only clone one dimension array.
        for (int i = 0; i < graph.vertexNum; i++) {
            builder.vertexArcs[i] = graph.vertexArcs[i].clone();
        }
        return new Graph(builder);
    }

    public List<Integer> vexesTo(int w) {
        List<Integer> vexesTo = new ArrayList<Integer>();
        for (int i = 0; i < vertexNum; i++) {
            if (vertexArcs[i][w] >= 0) {
                vexesTo.add(i);
            }
        }
        return vexesTo;
    }

    public static class Builder implements name.huzhenbo.java.patterns.builder.Builder<Graph> {
        private int vertexNum;
        private int[][] vertexArcs;

        public Builder(int vertexNum) {
            this.vertexNum = vertexNum;
            vertexArcs = new int[vertexNum][vertexNum];
            for (int i = 0; i < vertexNum; i++) {
                for (int j = 0; j < vertexNum; j++) {
                    vertexArcs[i][j] = -1;
                }
            }
        }

        public Graph build() {
            return new Graph(this);
        }

        public Builder addArc(int v1, int v2, int weight) {
            vertexArcs[v1][v2] = weight;
            return this;
        }
    }
}
